package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 二叉树的最近公共祖先
 * @date 2022/9/30 17:11
 */
public class Demo42 {

     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
              if(root==null||p==root||q==root){
                  return root;
              }

        TreeNode left=lowestCommonAncestor(root.left,p,q);

        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //都不为空，证明两个再左右分支上
        if(left!=null&&right!=null){
            return root;
        }
        //谁不为空，返回另外一个
         return left==null?right:left;
    }
}
